/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package ua.yandex.mergesort;

/**
 *
 * @author vlad
 */
class Merge implements Runnable {

    private int[] array;
    private int[] tempArray;
    private int left1;
    private int left2;
    private int right1;
    private int right2;
    private int tLeft;

    public Merge(int[] array, int left1, int right1, int left2, int right2,
            int[] tempArray, int tLeft) {
        if (array == null) {
            throw new NullPointerException("Null array reference");
        }
        this.tempArray = tempArray;
        this.tLeft = tLeft;
        this.array = array;
        this.left1 = left1;
        this.left2 = left2;
        this.right1 = right1;
        this.right2 = right2;
    }

    private int binarySearchR(int x, int left, int right) {
        int ll = left;
        int rr = Math.max(right + 1, left);
        while (ll < rr) {
            int median = (ll + rr) / 2;
            if (x <= array[median]) {
                rr = median;
            } else {
                ll = median + 1;
            }
        }
        return rr;
    }

    @Override
    public void run() {
        int n1 = right1 - left1 + 1;
        int n2 = right2 - left2 + 1;
        if (n1 < n2) {
            int temp = n1;
            n1 = n2;
            n2 = temp;
            temp = left1;
            left1 = left2;
            left2 = temp;
            temp = right1;
            right1 = right2;
            right2 = temp;
        }
        if (n1 != 0) {
            int q1 = (left1 + right1) / 2;
            int q2 = binarySearchR(array[q1], left2, right2);
            int q3 = tLeft + (q1 - left1) + (q2 - left2);
            tempArray[q3] = array[q1];
            Merge m1 = new Merge(array, left1, q1 - 1, left2, q2 - 1,
                    tempArray, tLeft);
            Merge m2 = new Merge(array, q1 + 1, right1, q2, right2,
                    tempArray, q3 + 1);
            Thread t = new Thread(m1);
            t.start();
            m2.run();
            try {
                t.join();
            } catch (InterruptedException e) {
                System.out.println("Merging failed");
            }
        }
    }

}
